package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/3/18
 */
public class MaxProduct {

    public static void main(String[] args) {

    }

    public static int maxProduct(TreeNode root) {
        long treeSum = initTreeVal(root);
        helper(root, treeSum);
        return (int) (max % 1000000007);
    }

    static long max = Long.MIN_VALUE;

    private static void helper(TreeNode root, long sum) {
        if ( root != null ) {
            long val = treeSums.get(root);
            long oth = sum - val;
            if ( val != 0 && oth != 0 )
                max = Math.max(val * oth, max);
            helper(root.left, sum);
            helper(root.right, sum);
        }
    }

    static Map<TreeNode, Long> treeSums = new HashMap<>();

    private static long initTreeVal(TreeNode node) {
        if ( node != null ) {
            long sum = initTreeVal(node.left) + initTreeVal(node.right) + node.val;
            treeSums.put(node, sum);
            return sum;
        }
        return 0;
    }

}
